package leetcode.search.comon;

import lombok.extern.slf4j.Slf4j;

import java.util.HashMap;
import java.util.Map;

@Slf4j
public class SearchUtils {

    /**
     * 将一个升序数组平移元素之后,在得到的新数组中求指定key的位置,不存在则返回-1
     * 原数组为[10, 14, 16, 19, 21, 23, 35, 37, 49, 59]
     * 平移之后为[21, 23, 35, 37, 49, 59, 10, 14, 16, 19]
     *
     * @param array
     * @param key
     * @return 元素存在则返回key的索引, 不存在则返回-1
     */
    public static int findTheKey(int[] array, int key) {


        if (array == null || array.length == 0) {
            return -1;
        }
        int indexOfMax = findMaxByBinarySearch(array, 0, array.length - 1);


        int firstIndex = BinarySearch(array, 0, indexOfMax, key);
        int secondIndex = BinarySearch(array, indexOfMax + 1, array.length - 1, key);


        return firstIndex > secondIndex ? firstIndex : secondIndex;
    }

    /**
     * 标准二分查找,在 升序数组 array中查找key
     *
     * @param array
     * @param left  左边界
     * @param right 右边界
     * @param key
     * @return
     */
    public static int BinarySearch(int[] array, int left, int right, int key) {

        if (array == null || array.length == 0) {
            return -1;
        }
        if (left > right) {
            return -1;
        }
        if (checkIndex(left, array) == false || checkIndex(right, array) == false) {
            return -1;
        }
        if (left == right && array[left] == key) {
            return left;
        }
        int index = -1;
        while (left <= right) {
            int mid = (left + right) / 2;

            if (array[mid] == key) {
                index = mid;
                break;
            }
            if (array[mid] < key) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return index;
    }

    private static boolean checkIndex(int index, int[] array) {
        if (index >= 0 && index <= array.length - 1) {
            return true;
        }
        return false;
    }

    /**
     * 将一个升序数组平移元素之后,在得到的新数组中求出最大值的索引
     * 原数组为[10, 14, 16, 19, 21, 23, 35, 37, 49, 59]
     * 平移之后为[21, 23, 35, 37, 49, 59, 10, 14, 16, 19]
     * 求出 最大值59 在新数组中的位置
     *
     * @param array
     * @param left
     * @param right
     * @return
     */
    public static int findMaxByBinarySearch(int[] array, int left, int right) {


        if (left > right) {
            return -1;
        }
        if (left == right) {
            return left;
        }
        int index = -1;
        int head = array[left];
        while (left <= right) {

            if (left == right) {
                index = left;
                break;
            }
            if (left + 1 == right) {
                index = array[left] > array[right] ? left : right;
                break;
            }
            int mid = (right + left) / 2;

            if (array[mid] > array[mid - 1] && array[mid] > array[mid + 1]) {
                index = mid;
                break;
            }
            if (array[mid] < head) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }

        return index;
    }

    public static int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return new int[]{-1, -1};
        }
        if (nums.length == 1 && target == nums[0]) {
            return new int[]{0, 0};
        }
        int leftIndex = getTheLeftIndex(nums, target);
        int rightIndex = getTheRightIndex(nums, target);
        int[] range = new int[]{-1, -1};
        if (leftIndex <= rightIndex) {
            range = new int[]{leftIndex, rightIndex};
        }
        return range;
    }

    public static int getTheRightIndex(int[] nums, int target) {
        // 5,7,7,8,8,10
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (target >= nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }

    public static int getTheLeftIndex(int[] nums, int target) {
        // 5,7,7,8,8,10
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (target <= nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static int searchInsert(int[] nums, int target) {
        if (nums == null) {
            return -1;
        }
        if (nums.length == 0) {
            return 0;
        }
        if (target > nums[nums.length - 1]) {
            return nums.length;
        }
        if (target < nums[0]) {
            return 0;
        }
        int left = 0;
        int right = nums.length - 1;
        int index = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                index = mid;
                break;
            }
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if (index == -1) {
            index = left;
        }
        return index;
    }

    public static boolean isValidSudoku(char[][] board) {
        // 验证行
        for (int i = 0; i < 9; i++) {
            char[] line = board[i];
            if (checkLine(line)) {
                return false;
            }
        }

        // 验证列 i 为列
        for (int i = 0; i < 9; i++) {
            char[] column = new char[9];
            // j 为行
            for (int j = 0; j < 9; j++) {
                column[j] = board[j][i];
            }
            if (checkLine(column)) {
                return false;
            }
        }

        // 验证3x3宫
        for (int i = 0; i < 9; i = i + 3) {
            for (int j = 0; j < 9; j = j + 3) {
                char[] matrix = get33Matrix(i, j, board);
                if (checkLine(matrix)) {
                    return false;
                }
            }
        }

        return true;

    }

    private static char[] get33Matrix(int m, int n, char[][] board) {
        char[] matrix = new char[9];
        int i = 0;
        for (int x = m; x < m + 3; x++) {
            for (int y = n; y < n + 3; y++) {
                matrix[i] = board[x][y];
                i++;
            }
        }
        return matrix;
    }

    private static boolean checkLine(char[] line) {
        boolean result = false;
        Map<Character, Boolean> existNum = new HashMap<>();
        for (int j = 0; j < line.length; j++) {
            char key = line[j];
            if (key == '.') {
                continue;
            }
            if (existNum.isEmpty()) {
                existNum.put(key, true);
                continue;
            }
            Boolean value = existNum.get(key);
            if (value != null && value) {
                result = true;
                break;
            }
            existNum.put(key, true);
        }
        return result;
    }

    public static void printSudoku(char[][] board) {
        System.out.println("==================");
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("==================");
    }

    public static void printSudoku(char[][] board, int row, int col, char num) {
        System.out.println("==================");
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (i == row && j == col) {
                    System.out.print(num + " ");
                } else {
                    System.out.print(board[i][j] + " ");
                }
            }
            System.out.println();
        }
        System.out.println("==================");
    }

    public static void solveSudoku(char[][] board) {
        int row = 0;
        int col = 0;
        char[] nums = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
        backTraceForSolveSudoku(row, col, board, nums);
    }

    private static boolean backTraceForSolveSudoku(int row, int col, char[][] board, char[] nums) {
        if (row == 8 && col == 9) {
            return true;
        }
        if (col == 9) {
            col = col % 9;
            row++;
        }
        if (board[row][col] == '.') {
            for (int i = 0; i < 9; i++) {
                if (repeatCheck(row, col, board, nums[i])) {
                    continue;
                }
                board[row][col] = nums[i];
                boolean result = backTraceForSolveSudoku(row, col + 1, board, nums);
                if (result) {
                    return true;
                }
                board[row][col] = '.';
            }
        } else {
            boolean result = backTraceForSolveSudoku(row, col + 1, board, nums);
            if (result) {
                return true;
            }
        }
        return false;
    }

    private static boolean repeatCheck(int row, int col, char[][] board, char num) {
        // 检查行和列是否重复
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num || board[i][col] == num) {
                return true;
            }
        }
        // 检查所在九宫格是否重复
        int x = row / 3 * 3;
        int y = col / 3 * 3;
        for (int i = x; i < x + 3; i++) {
            for (int j = y; j < y + 3; j++) {
                if (board[i][j] == num) {
                    return true;
                }
            }
        }
        // 默认不重复
        return false;
    }

    public static int simpleMySqrt(int x) {
        if (x < 0) {
            return -1;
        }
        if (x == 0) {
            return 0;
        }
        int left = 1;
        int right = x / 2 + 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if ((long) mid * mid <= x && (long) (mid + 1) * (mid + 1) > x) {
                return mid;
            }
            if ((long) mid * mid < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    public static int simpleMySqrt2(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }

    public static int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = (int) Math.exp(0.5 * Math.log(x));
        if ((ans + 1) * (ans + 1) <= x) {
            return ans + 1;
        }
        return ans;
    }

    /**
     * 找到旋转数组中最小值的索引
     *
     * @param array
     * @param left
     * @param right
     * @return
     */
    public static int findMinByBinarySearch(int[] array, int left, int right) {
        if (left > right || left < 0 || right > array.length - 1) {
            return -1;
        }
        if (left == right) {
            return left;
        }
        int theFirstNum = array[left];
        int theLastNum = array[right];
        // 如果没有旋转或者正好旋转成了原数组
        if (theFirstNum < theLastNum) {
            return left;
        }
        // 旋转了
        while (left <= right) {
            if (left == right) {
                return right;
            }
            int mid = left + (right - left) / 2;
            if (array[mid] >= theFirstNum) {
                left = mid + 1;
            } else if (array[mid] < theFirstNum) {
                right = mid;
            }
        }
        return -1;
    }

    public static int findMin(int[] nums) {
        int index = findMinByBinarySearch(nums, 0, nums.length - 1);
        return nums[index];
    }

    public static int findMinWithRepeatedNum(int[] nums) {
        int index = findMinByBinarySearchWithRepeatedNum(nums, 0, nums.length - 1);
        return nums[index];
    }

    public static int findMinByBinarySearchWithRepeatedNum(int[] array, int left, int right) {
        if (left > right || left < 0 || right > array.length - 1) {
            return -1;
        }
        if (left == right) {
            return left;
        }
        int firstNum = array[left];
        // 去除首部与首元素重复的元素，仅保留一次首元素
        while (left < right) {
            if (array[left + 1] == firstNum) {
                left = left + 1;
            } else {
                break;
            }
        }
        // 去除尾部所有与首元素重复的元素
        while (left < right) {
            if (array[right] == firstNum) {
                right = right - 1;
            } else {
                break;
            }
        }
        // 数组中仅剩余一个元素，说明原数组所有元素均相同
        if (left == right) {
            return left;
        }
        // 剩余部分是没有被旋转的形态，最小值在第一位
        if (array[right] > array[left]) {
            return left;
        }
        int newFirstNum = array[left];
        // 剩余部分是被旋转的形态，最小值不在第一位
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (left == right) {
                return right;
            }
            // 与首元素相同时，也直接往右侧缩小范围
            if (array[mid] >= newFirstNum) {
                left = mid + 1;
            } else if (array[mid] < newFirstNum) {
                right = mid;
            }
        }
        return -1;
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            int[] row = matrix[i];
            if (searchRow(row, target)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 使用二分查找判断一个数是否存在于数组中
     *
     * @param row
     * @param target
     * @return
     */
    private static boolean searchRow(int[] row, int target) {
        int left = 0;
        int right = row.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (row[mid] == target) {
                return true;
            } else if (row[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }

    public static int maxValue(int n, int index, int maxSum) {
        int left = 1;
        int right = maxSum;
        while (left <= right) {
            if (left == right) {
                if (valid(left, index, n, maxSum)) {
                    return left;
                } else {
                    return -1;
                }
            }
            if (left == right - 1) {
                if (valid(right, index, n, maxSum)) {
                    return right;
                } else {
                    right--;
                }
            }
            int mid = left + (right - left) / 2;
            if (valid(mid, index, n, maxSum)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    public static boolean valid(int mid, int index, int n, int maxSum) {
        int left = index;
        int right = n - index - 1;
        return mid + cal(mid, left) + cal(mid, right) <= maxSum;
    }

    public static long cal(int big, int length) {
        if (length + 1 < big) {
            int small = big - length;
            return (long) (big - 1 + small) * length / 2;
        } else {
            int ones = length - (big - 1);
            return (long) big * (big - 1) / 2 + ones;
        }
    }


    private static boolean valid2(int mid, int index, int n, int maxSum) {
        int[] nums = new int[n];
        nums[index] = mid;
        int curSum = 0;
        curSum += nums[index];
        for (int i = index - 1; i >= 0; i--) {
            if (nums[i + 1] > 1) {
                nums[i] = nums[i + 1] - 1;
            } else if (nums[i + 1] == 1) {
                nums[i] = 1;
            }
            curSum += nums[i];
            if (curSum > maxSum) {
                return false;
            }
        }
        for (int i = index + 1; i < n; i++) {
            if (nums[i - 1] > 1) {
                nums[i] = nums[i - 1] - 1;
            } else if (nums[i - 1] == 1) {
                nums[i] = 1;
            }
            curSum += nums[i];
            if (curSum > maxSum) {
                return false;
            }
        }
        return true;
    }

    public static boolean isPerfectSquare(int num) {
        if (num <= 0) {
            return false;
        }
        if (num == 1) {
            return true;
        }
        if (num == 2) {
            return false;
        }
        int left = 2;
        int right = num / 2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            long square = (long) mid * mid;
            if (square == num) {
                return true;
            } else if (square > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }

    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        if (totalLength % 2 == 1) {
            int midIndex = totalLength / 2;
            double median = getKthElement(nums1, nums2, midIndex + 1);
            return median;
        } else {
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            return median;
        }
    }

    public static int getKthElement(int[] nums1, int[] nums2, int k) {
        /* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
         * 这里的 "/" 表示整除
         * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
         * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
         * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
         * 这样 pivot 本身最大也只能是第 k-1 小的元素
         * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
         * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
         * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
         */

        int length1 = nums1.length, length2 = nums2.length;
        int index1 = 0, index2 = 0;

        while (true) {
            // 边界情况
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }
            // 正常情况
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }

    public static int findDuplicate(int[] nums) {

        int n = nums.length;
        int l = 1, r = n - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                if (nums[i] <= mid) {
                    cnt++;
                }
            }
            if (cnt <= mid) {
                l = mid + 1;
            } else {
                r = mid - 1;
                ans = mid;
            }
        }
        return ans;

    }

    public static boolean search81(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return false;
        }
        if (n == 1) {
            return nums[0] == target;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
                ++l;
                --r;
            } else if (nums[l] <= nums[mid]) {
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return false;
    }

    public static int findPeakElement(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int num = nums[mid];
            if (mid == 0) {
                if (num > nums[mid + 1]) {
                    return mid;
                } else {
                    left = mid + 1;
                }
                continue;
            }
            if (mid == nums.length - 1) {
                if (num > nums[mid - 1]) {
                    return mid;
                } else {
                    right = mid - 1;
                }
                continue;
            }
            if (num > nums[mid - 1] && num > nums[mid + 1]) {
                return mid;
            }
            if (num > nums[mid - 1]) {
                left = mid + 1;
                continue;
            }
            if (num > nums[mid + 1]) {
                right = mid - 1;
                continue;
            }
            left = mid + 1;
        }
        return nums[left] > nums[right] ? left : right;
    }

    public static boolean searchMatrixII(int[][] matrix, int target) {
        for (int[] rowNum : matrix) {
            int left = 0;
            int right = rowNum.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (rowNum[mid] == target) {
                    return true;
                } else if (rowNum[mid] > target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return false;
    }
}
